The present invention relates to an adaptive segment control for a multi-segment cache memory. In particular, the present invention relates to an adaptive segment control which performs hit ratio simulations on virtual cache tables based on memory instructions received from a host computer.
Cache memories are used within computer storage systems. In a magnetic storage system, for example, the cache memory is located within a disk controller which controls operation of a magnetic disk drive. The disk controller is configured for connection with a host computer through a data bus, such as a small computer systems interface (SCSI). The disk controller passes data back and forth between the disk drive and the host computer in response to memory instructions or commands generated by the host computer.
The magnetic disk drive stores the data on the surface of a rotating magnetic disk. The disk surface includes a plurality of generally concentric data tracks. Each data track is divided into sectors or blocks. In one typical disk drive, each data track is divided into 35 blocks, each block including 512 bytes of data. A byte of data is represented by an individual address in the storage system.
The memory instructions cause the disk controller to initiate read and write operations within the disk drive. Each memory instruction includes a starting address, a block length (the number of blocks required) and an instruction type, such as read or write. After the disk controller receives a read instruction, for example, the controller signals the disk drive to retrieve the required number of blocks beginning at the starting address. After the data has been retrieved, the disk drive controller passes the data back to the host computer.
The cache memory improves storage system performance by reducing the number of times the controller must go to the disk to retrieve data. The cache memory stores the most recently accessed data in random access memory (RAM). When the host computer runs a particular software application, the input/output patterns seen by the disk drive controller tend to repeat. Therefore, there is a greater chance that data obtained from the disk will be used again. When the host computer requests retrieval of data that is in the cache memory, the controller does not have to retrieve the information from the disk but can retrieve it directly from the cache memory. Because the cache memory has a much faster data access time than the disk drive, retrieving the data directly from the cache memory substantially reduces the data access time seen by the host computer.
The cache memory includes a cache buffer and a cache table. In one embodiment, the cache buffer can store up to 192K bytes of data. The cache table maintains a list of the data present in the cache buffer by recording the starting addresses of the data retrieved from the disk. When the controller receives a write instruction that corresponds to addresses present in the cache memory, it updates the cache table such that it no longer indicates the data is present within the buffer. This prevents old data from being read from the cache buffer.
When the controller receives a read instruction, it refers to the cache table to determine whether the requested data is present in the cache buffer. If the data is not present in the cache buffer (cache miss), the controller retrieves the data from the disk and relays the data to the host computer. The controller also loads the data into the cache buffer and updates the cache table. A cache hit occurs when the data requested by the host computer is present in the cache buffer. In this situation, the controller retrieves the information directly from the buffer and transmits the data to the host computer. The ratio of cache hits to cache misses is a measure of cache memory performance.
In a multi-segment cache, the cache buffer is divided into segments. The number of segments in the cache buffer is known as the segmentation level. By segmenting the cache buffer, the controller can perform "look ahead" operations by retrieving excess blocks to fill an entire segment. Because memory operations tend to form repetitive and somewhat predictable patterns, the host computer will likely request data from the next consecutive blocks. The segmentation level determines the number of blocks in each segment and therefore determines the number of excess blocks retrieved. The greater the segmentation level, the smaller the number of blocks in each segment. Performance of the cache memory may be controlled by controlling the number of excess blocks retrieved in a read operation.
The optimum segmentation level depends upon the particular software application running on the host computer. Because the host computer frequently switches between various applications, a selected segmentation level may not achieve the desired performance over a wide range of applications. Therefore, a cache having an adaptive segment control is desired.
Heuristic programming is one method of controlling segmentation level. A statistical performance analysis is performed on the cache memory and these results are applied to a set of rules. The variables applied to the rules include, among others, the number of blocks in each read that are a cache hit and the number of blocks that are a cache miss. However, there is simply not enough information in past statistical performance to predict a preferred segment level. Because there are many exceptions to the rules, heuristic programs do not provide accurate, dependable results. Therefore, there is a continuing need for a multi-segment cache having improved segment control.